import java.util.Arrays;

/**
 * @author LKQ
 * @date 2022/2/25 11:03
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.largestSumAfterKNegations(new int[] {2, -3, -1, 5, -4}, 2);
    }
    public int largestSumAfterKNegations(int[] nums, int k) {
        int sum = 0;
        Arrays.sort(nums);
        int min = nums[0];
        if (min > 0) {
            // 最小值大于0, 全是正数
            for (int num: nums) {
                sum += num;
            }
            if(k % 2 == 1) {
                // 修改奇数次
                sum -= 2 * min;
            }
        }else if (min == 0) {
            for (int num: nums) {
                sum += num;
            }
        }else {
            // 最小值小于0，统计小于0的个数, maxMin记录最大的负数, minPositive 记录最小的正数
            int cnt = 0, maxNegative = Integer.MIN_VALUE, minPositive = Integer.MAX_VALUE;
            boolean hasZero = false;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < 0) {
                    cnt++;
                    maxNegative = Math.max(maxNegative, nums[i]);
                }else if (nums[i] == 0) {
                    hasZero = true;
                }else {
                    minPositive = Math.min(minPositive, nums[i]);
                }
            }

            if (cnt < k) {
                // 小于0的个数小于k, 这些负数全部转换为正数
                if (hasZero) {
                    // 有 0
                    for (int i = 0; i < nums.length; i++) {
                        sum += nums[i] < 0 ? -nums[i] : nums[i];
                    }
                }else {
                    // 没有0， 负数需要全部转为正数，剩下 k - cnt次
                    for (int i = 0; i < nums.length; i++) {
                        sum += nums[i] < 0 ? -nums[i] : nums[i];
                    }
                    if ((k - cnt) % 2 == 1) {
                        if (Math.abs(maxNegative) > Math.abs(minPositive)) {
                            sum -= 2 * minPositive;
                        }else {
                            sum -= 2 * (-maxNegative);
                        }
                    }
                }
            }else if (cnt == k){
                for (int i = 0; i < nums.length; i++) {
                    sum += nums[i] < 0 ? -nums[i] : nums[i];
                }
            }else {
                for (int i = 0; i < nums.length; i++) {
                    if (i < k) {
                        sum += (-nums[i]);
                    }else {
                        sum += nums[i];
                    }
                }
            }
        }
        return sum;
    }
}
